﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using Qiang.Topology.Geometries;

namespace Qiang.Data
{
    public class PolygonBuilder
    {

        #region 初始化

        public PolygonBuilder(IVectorSet dataset)
        {
            _shapeLst = dataset.ShapeList;
            AngleDic = new Dictionary<INodeShape, List<ISegmentShape>>();
            ClockWiseParts = new List<IPart>();        //顺时针Part
            CounterClockWiseParts = new List<IPart>(); //逆时针Part
        }

        #endregion


        #region 属性

        IShapeList _shapeLst;

        /// <summary>
        /// 图形集合。
        /// </summary>
        public IShapeList ShapeLst
        {
            get { return _shapeLst; }
            set { _shapeLst = value; }
        }

        Dictionary<INodeShape, List<ISegmentShape>> AngleDic; //所有节点关联的弧段的角度排序
        List<IPart> ClockWiseParts;        //顺时针Part
        List<IPart> CounterClockWiseParts; //逆时针Part

        #endregion


        #region 构造多边形

        /// <summary>
        /// 根据节点和线构造多边形
        /// </summary>
        public void BuildPolygon()
        {
            if (_shapeLst.Count <= 1) return;

            #region

            //在构造多边形之前，应先遍历所有的多边形，因为在构造之前已存在的多边形可能移动过坐标变成了反向的多边形，所以要将反向多边形变成正向多边形再进行其它的构造

            //foreach (Polygon polygon in this._polygons)
            //{
            //    bool b = this.IsEffectivePolygon(polygon.points);
            //    if (b == true) continue;

            //    foreach (DerectionSegment segment in polygon.SegmentCollection)
            //    {
            //        if (segment.CurrentDerection == segment.Segment.FirstusedDerection)
            //        {
            //            if (segment.CurrentDerection == Derection.Left)
            //            {
            //                segment.CurrentDerection = Derection.Right;
            //                segment.Segment.FirstusedDerection = Derection.Right;
            //                segment.Segment.SecondUsedDerection = Derection.Left;
            //            }
            //            else
            //            {
            //                segment.CurrentDerection = Derection.Left;
            //                segment.Segment.FirstusedDerection = Derection.Left;
            //                segment.Segment.SecondUsedDerection = Derection.Right;
            //            }
            //        }
            //        else
            //        {
            //            if (segment.CurrentDerection == Derection.Left)
            //            {
            //                segment.CurrentDerection = Derection.Right;
            //                segment.Segment.FirstusedDerection = Derection.Left;
            //                segment.Segment.SecondUsedDerection = Derection.Right;
            //            }
            //            else
            //            {
            //                segment.CurrentDerection = Derection.Left;
            //                segment.Segment.FirstusedDerection = Derection.Right;
            //                segment.Segment.SecondUsedDerection = Derection.Left;
            //            }
            //        }
            //    }

            //}

            #endregion

            //思路：
            //1 筛选有效图形。将悬挂弧段、节点删除。自封闭弧段不属于悬挂弧段。
            //2 计算所有节点关联的弧段的角度，并将弧段按角度排序。
            //3 利用左转算法，将有效图形构造成封闭的Part。为分两部分存储，顺时针和逆时针。
            //4 构造多边形。将所有构造成的Part组织判断是否单一多边形还是有岛多边形。判断方法为顺时针Part是否包含逆时针Part.

            AngleDic.Clear();
            ClockWiseParts.Clear();
            CounterClockWiseParts.Clear();

            IShapeList EffectiveShps = new ShapeList();
            #region 第一步：筛选有效图形

            //筛选悬挂弧段、节点            
            foreach (IShape shp in _shapeLst)
            {
                if (shp.ShapeType != ShapeType.Segment) continue;
                ISegmentShape segment = shp as ISegmentShape;
                if (segment.StartNode.SegmentCollection.Count == 1 || segment.EndNode.SegmentCollection.Count == 1)
                {
                    if (segment.StartNode.Equals(segment.EndNode) == false) continue;
                }
                EffectiveShps.Add(segment);
            }

            #endregion

            List<IShape> nodeLst = _shapeLst.Where(n => n.ShapeType == ShapeType.Node).ToList();

            #region 第二步：计算所有节点关联弧段的角度

            foreach (IShape shp in nodeLst)
            {
                if (shp.ShapeType != ShapeType.Node) continue;
                INodeShape node = shp as INodeShape;
                if (node == null) continue;

                AngleDic.Add(node, new List<ISegmentShape>());

                Dictionary<double, ISegmentShape> CurrentAngleDic = new Dictionary<double, ISegmentShape>();
                foreach (ISegmentShape segment in node.SegmentCollection)
                {
                    double angle = ComputeSegmentAngle(node, segment);
                    CurrentAngleDic.Add(angle, segment);
                }
                var segments = CurrentAngleDic.OrderBy(angle => angle.Key);
                foreach (var segment in segments)
                {
                    AngleDic[node].Add(segment.Value);
                }
            }

            #endregion


            #region 第三步：构造封闭Part

            foreach (IShape shp in nodeLst)
            {
                if (shp.ShapeType != ShapeType.Node) continue;
                INodeShape node = shp as INodeShape;
                if (node == null) continue;

                ISegmentShape startSegment = null;
                SegmentDirection currentDrection = SegmentDirection.None;
                INodeShape nextNode = null;

                for (int i = 0; i < AngleDic[node].Count; i++)
                {
                    startSegment = AngleDic[node][i];
                    if (node.Equals(startSegment.StartNode))
                    {
                        currentDrection = SegmentDirection.Left;
                        nextNode = startSegment.EndNode;
                    }
                    else
                    {
                        currentDrection = SegmentDirection.Right;
                        nextNode = startSegment.StartNode;
                    }

                    if (startSegment.UsedNum == 2 || (startSegment.UsedNum == 1 && startSegment.FirstusedDerection == currentDrection)) continue;

                    if (i == AngleDic[node].Count - 1)
                    {
                        //如果是最后一条弧段，特殊对待
                    }

                    //如果弧段自己本身是封闭的
                    if (startSegment.StartNode.Equals(startSegment.EndNode))
                    {
                        if (startSegment.UsedNum == 0)
                        {
                            startSegment.FirstusedDerection = currentDrection;
                        }
                        else
                        {
                            startSegment.SecondUsedDerection = currentDrection;
                        }
                        startSegment.UsedNum += 1;

                        bool isClockWise = IsClockWisePolygon(startSegment.Coordinates);
                        if (isClockWise)
                        {
                            IPart ClockPart = new Part();
                            ClockPart.SegmentCollection.Add(new DirectionalSegment(currentDrection, startSegment));
                            ClockWiseParts.Add(ClockPart);
                            IPart CounterClockPart = new Part();
                            CounterClockPart.SegmentCollection.Add(new DirectionalSegment(DirectionReverse.Reverse(currentDrection), startSegment));
                            CounterClockWiseParts.Add(CounterClockPart);
                        }
                        else
                        {
                            IPart ClockPart = new Part();
                            ClockPart.SegmentCollection.Add(new DirectionalSegment(DirectionReverse.Reverse(currentDrection), startSegment));
                            ClockWiseParts.Add(ClockPart);
                            IPart CounterClockPart = new Part();
                            CounterClockPart.SegmentCollection.Add(new DirectionalSegment(currentDrection, startSegment));
                            CounterClockWiseParts.Add(CounterClockPart);
                        }
                        continue;
                    }
                    else
                    {
                        BuildParts(startSegment, node, nextNode);
                    }

                }
            }

            #endregion


            #region 第四步：构造多边形

            BuildPolygonByPart();

            #endregion

        }

        /// <summary>
        /// 根据计算好的封闭的Part，进行岛的判断，最终构成多边形。
        /// </summary>
        void BuildPolygonByPart()
        {
            foreach (IPart shell in ClockWiseParts)
            {
                IPolygonShape polygonShp = new PolygonShape(shell);
                foreach (DirectionalSegment ds in shell.SegmentCollection)
                {
                    if (ds.Derection == SegmentDirection.Left) ds.Segment.RightPolygon = polygonShp;
                    else ds.Segment.LeftPolygon = polygonShp;
                }
                Geometry polyShell = shell.ToPolygon() as Polygon;
                foreach (IPart hole in CounterClockWiseParts)
                {
                    if (Equals(shell, hole)) continue;
                    IPolygon polyHole = hole.ToPolygon();
                    if (!polyShell.Contains(polyHole)) continue;
                    if (polyShell.Equals(polyHole)) continue;
                    polygonShp.Holes.Add(hole);
                    foreach (DirectionalSegment ds in hole.SegmentCollection)
                    {
                        if (ds.Derection == SegmentDirection.Left) ds.Segment.RightPolygon = polygonShp;
                        else ds.Segment.LeftPolygon = polygonShp;
                    }
                }
                _shapeLst.Add(polygonShp);
            }
        }

        /// <summary>
        /// 获得弧段segment在端点Node处与X轴的夹角
        /// </summary>
        /// <param name="node"></param>
        /// <param name="segment"></param>
        /// <returns></returns>
        double ComputeSegmentAngle(INodeShape node, ISegmentShape segment)
        {
            Coordinate pt = null;

            if (node.Equals(segment.StartNode))
            {
                if (segment.VertexCollection.Count > 0)
                {
                    pt = segment.VertexCollection[0].Point;
                }
                else
                {
                    pt = segment.EndNode.Point;
                }
            }
            else
            {
                if (segment.VertexCollection.Count > 0)
                {
                    pt = segment.VertexCollection[segment.VertexCollection.Count - 1].Point;
                }
                else
                {
                    pt = segment.StartNode.Point;
                }
            }

            double dx = pt.X - node.Point.X;
            double dy = pt.Y - node.Point.Y;

            double angle = 0;

            if (dx == 0)
            {
                if (dy > 0)
                {
                    angle = Math.PI / 2;
                }
                else
                {
                    angle = Math.PI * 3 / 2;
                }
            }
            else
            {
                if (dx > 0 && dy >= 0)
                {
                    angle = Math.Atan(dy / dx);
                }
                else if (dx < 0 && dy >= 0)
                {
                    angle = Math.PI - Math.Atan(Math.Abs(dy / dx));
                }
                else if (dx < 0 && dy <= 0)
                {
                    angle = Math.PI + Math.Atan(dy / dx);
                }
                else if (dx > 0 && dy < 0)
                {
                    angle = Math.PI * 2 - Math.Atan(Math.Abs(dy / dx));
                }
            }

            return angle;

        }


        /// <summary>
        /// 根据起始结点起始弧段构建Parts.
        /// </summary>
        /// <param name="startSegment"></param>
        /// <param name="startNode"></param>
        /// <param name="shareNode"></param>
        /// <param name="polygons"></param>
        void BuildParts(ISegmentShape startSegment, INodeShape startNode, INodeShape shareNode)
        {
            if (startSegment.UsedNum == 2) return;

            SegmentDirection currentDerection = SegmentDirection.None;
            if (startSegment.StartNode.Equals(startNode))
            {
                currentDerection = SegmentDirection.Left;
            }
            else
            {
                currentDerection = SegmentDirection.Right;
            }
            if (startSegment.UsedNum == 1 && startSegment.FirstusedDerection == currentDerection) return;

            Dictionary<ISegmentShape, SegmentDirection> segments = new Dictionary<ISegmentShape, SegmentDirection>();
            segments.Add(startSegment, currentDerection);
            bool b = this.ComputeSegments(startSegment, startNode, startSegment, shareNode, ref segments);
            if (b == true)
            {
                List<Coordinate> coors = new List<Coordinate>();
                int index = 0;
                foreach (KeyValuePair<ISegmentShape, SegmentDirection> segment in segments)
                {
                    if (index == 0)
                    {
                        if (segment.Value == SegmentDirection.Left)
                        {
                            coors.Add(segment.Key.StartNode.Point);
                        }
                        else
                        {
                            coors.Add(segment.Key.EndNode.Point);
                        }
                    }
                    if (segment.Value == SegmentDirection.Left)
                    {
                        foreach (IVertexShape vertex in segment.Key.VertexCollection)
                        {
                            coors.Add(vertex.Point);
                        }
                        coors.Add(segment.Key.EndNode.Point);
                    }
                    else
                    {
                        for (int i = segment.Key.VertexCollection.Count - 1; i >= 0; i--)
                        {
                            coors.Add(segment.Key.VertexCollection[i].Point);
                        }
                        coors.Add(segment.Key.StartNode.Point);
                    }
                    index++;
                }

                //先判断这个多边形是不是顺时针。
                //如果是逆时针，则弧段使用次数前面就不能加1
                bool isClock = this.IsClockWisePolygon(coors);
                if (isClock == true)
                {
                    #region 判断特殊情况判断。
                    //自相交的多边形，无法判断是顺时针还是逆时针，这个多边形是有效但已经存在了。
                    List<ISegmentShape> temSegments = new List<ISegmentShape>();
                    foreach (KeyValuePair<ISegmentShape, SegmentDirection> segment in segments)
                    {
                        temSegments.Add(segment.Key);
                    }
                    List<IPart> parts = ClockWiseParts.Where(p => p.ShapeType == ShapeType.Part).ToList();
                    foreach (IPart p in parts)
                    {
                        bool isExist = true;
                        foreach (SegmentShape segment in temSegments)
                        {
                            if (p.Segments.Contains(segment) == false)
                            {
                                isExist = false;
                            }
                            if (isExist == false)
                            {
                                break;
                            }
                        }
                        if (isExist == true) return;
                    }

                    #endregion

                    IPart part = new Part();
                    foreach (KeyValuePair<ISegmentShape, SegmentDirection> segment in segments)
                    {
                        if (segment.Key.UsedNum == 0)
                        {
                            segment.Key.FirstusedDerection = segment.Value;
                        }
                        else
                        {
                            segment.Key.SecondUsedDerection = segment.Value;
                        }
                        segment.Key.UsedNum += 1;
                        part.SegmentCollection.Add(new DirectionalSegment(segment.Value, segment.Key));
                    }
                    ClockWiseParts.Add(part);
                }
                else
                {
                    IPart part = new Part();
                    foreach (KeyValuePair<ISegmentShape, SegmentDirection> segment in segments)
                    {
                        if (segment.Key.UsedNum == 0)
                        {
                            segment.Key.FirstusedDerection = segment.Value;
                        }
                        else
                        {
                            segment.Key.SecondUsedDerection = segment.Value;
                        }
                        //segment.Key.UsedNum += 1;
                        part.SegmentCollection.Add(new DirectionalSegment(segment.Value, segment.Key));
                    }
                    CounterClockWiseParts.Add(part);
                }

                //以生成的多边形的最后一条弧段做为起始弧段递归调用本函数
                startSegment = segments.Last().Key;

                if (startSegment.StartNode.Equals(startNode))
                {
                    shareNode = startSegment.EndNode;
                }
                else
                {
                    shareNode = startSegment.StartNode;
                }
                BuildParts(startSegment, startNode, shareNode);
            }
            else
            {
                //Do nothing
            }

        }


        /// <summary>
        /// 根据起始弧段、起始节点、当前弧段、当前方向下当前弧段的结束节点查找构成Part的弧段。
        /// </summary>
        /// <param name="startSegment"></param>
        /// <param name="startNode"></param>
        /// <param name="CurrentSegment"></param>
        /// <param name="shareNode"></param>
        /// <param name="ExistSegments"></param>
        /// <returns></returns>
        bool ComputeSegments(ISegmentShape StartSegment, INodeShape StartNode, ISegmentShape CurrentSegment, INodeShape CurrentNode, ref Dictionary<ISegmentShape, SegmentDirection> ExistSegments)
        {
            ISegmentShape nextSegment = this.ComputeNextSegment(CurrentSegment, CurrentNode, ExistSegments);

            if (nextSegment == null) return false;
            if (nextSegment.Equals(StartSegment)) return false;

            SegmentDirection nextDerection = SegmentDirection.None;
            if (nextSegment.StartNode.Equals(CurrentNode))
            {
                nextDerection = SegmentDirection.Left;
            }
            else
            {
                nextDerection = SegmentDirection.Right;
            }         
            if (ExistSegments.Keys.Contains(nextSegment)) return false;
            ExistSegments.Add(nextSegment, nextDerection);
            if (nextSegment.StartNode.Equals(StartNode) || nextSegment.EndNode.Equals(StartNode))
            {
                return true;
            }
            if (nextSegment.StartNode.Equals(CurrentNode))
            {
                CurrentNode = nextSegment.EndNode;
            }
            else
            {
                CurrentNode = nextSegment.StartNode;
            }
            //递归调用再找寻下一条弧段
            return ComputeSegments(StartSegment, StartNode, nextSegment, CurrentNode, ref ExistSegments);
        }


        /// <summary>
        /// 查找当前弧段的下一条弧段.
        /// </summary>
        /// <param name="lastSegment"></param>
        /// <param name="shareNode"></param>
        /// <param name="ExistSegments"></param>
        /// <returns></returns>
        ISegmentShape ComputeNextSegment(ISegmentShape CurrentSegment, INodeShape CurrentNode, Dictionary<ISegmentShape, SegmentDirection> ExistSegments)
        {
            //计算当前节点相关联的弧段与当前弧段的夹角。           
            Coordinate Start = null;
            if (CurrentSegment.VertexCollection.Count == 0)
            {
                if (CurrentSegment.StartNode.Equals(CurrentNode))
                    Start = CurrentSegment.EndNode.Point;
                else
                    Start = CurrentSegment.StartNode.Point;
            }
            else
            {
                if (CurrentSegment.StartNode.Equals(CurrentNode))
                    Start = CurrentSegment.VertexCollection[CurrentSegment.VertexCollection.Count - 1].Point;
                else
                    Start = CurrentSegment.VertexCollection[0].Point;
            }
            double MinAngle = Math.PI * 2;
            ISegmentShape result = null;
            SegmentDirection Direction = SegmentDirection.None;
            foreach (ISegmentShape item in CurrentNode.SegmentCollection)
            {
                if (item.Equals(CurrentSegment)) continue;
                SegmentDirection CurrentDirection = SegmentDirection.None;
                Coordinate End = null;
                if (item.StartNode.Equals(CurrentNode))
                {
                    CurrentDirection = SegmentDirection.Left;
                    if (item.VertexCollection.Count == 0)
                        End = item.EndNode.Point;
                    else
                        End = item.VertexCollection[0].Point;
                }
                else
                {
                    CurrentDirection = SegmentDirection.Right;
                    if (item.VertexCollection.Count == 0)
                        End = item.StartNode.Point;
                    else
                        End = item.VertexCollection[item.VertexCollection.Count - 1].Point;
                }
                double angle = ComputeAngleOfTwoSegments(Start, CurrentNode.Point, End);
                if (angle < MinAngle)
                {
                    MinAngle = angle;
                    Direction = CurrentDirection;
                    result = item;
                }
            }
            if (result != null)
            {
                if (result.UsedNum == 2) return null;
                if (result.UsedNum == 1 && result.FirstusedDerection == Direction) return null;
                return result;
            }
            return result;
        }


        /// <summary>
        /// 判断这个多边形是顺时针还是逆时针
        /// </summary>
        /// <param name="polygon"></param>
        /// <returns></returns>
        bool IsClockWisePolygon(IList<Coordinate> polygon)
        {
            int right = 0;
            int left = 0;

            List<Coordinate[]> lines = new List<Coordinate[]>();
            Coordinate[] line = new Coordinate[2];
            line[0] = polygon[polygon.Count - 1];
            line[1] = polygon[0];
            lines.Add(line);
            for (int i = 0; i < polygon.Count - 1; i++)
            {
                line = new Coordinate[2];
                line[0] = polygon[i];
                line[1] = polygon[i + 1];
                lines.Add(line);
            }
            List<Coordinate> pts = new List<Coordinate>();
            for (int i = 1; i < polygon.Count; i++)
            {
                pts.Add(polygon[i]);
            }
            pts.Add(polygon[0]);

            for (int i = 0; i < pts.Count; i++)
            {
                double derection = QMath.QMath.PtAtLine(pts[i], lines[i]);

                if (derection > 0)
                {
                    left++;
                }
                else if (derection < 0)
                {
                    right++;
                }
                else
                {
                }
            }

            if (left > right)
            {
                return true;
            }
            else if (left < right)
            {
                return false;
            }
            else
            {

            }

            return true;
        }


        /// <summary>
        /// 计算两条弧段的夹角.
        /// </summary>
        /// <param name="Start">起始弧段与节点的邻点</param>
        /// <param name="Inflection">共享节点</param>
        /// <param name="End">其它弧段与节点的邻点</param>
        /// <returns></returns>
        double ComputeAngleOfTwoSegments(Coordinate Start, Coordinate node, Coordinate End)
        {
            double aa = (Start.X - node.X) * (Start.X - node.X) + (Start.Y - node.Y) * (Start.Y - node.Y);
            double bb = (node.X - End.X) * (node.X - End.X) + (node.Y - End.Y) * (node.Y - End.Y);
            double cc = (Start.X - End.X) * (Start.X - End.X) + (Start.Y - End.Y) * (Start.Y - End.Y);
            double cosValue = (aa + bb - cc) / (2 * Math.Sqrt(aa) * Math.Sqrt(bb));
            double angle = Math.Acos(cosValue);

            double coeff1 = 0.0f, coeff2 = 0.0f;
            if (Start.Y != node.Y)
            {
                coeff1 = (double)(node.X - Start.X) / (double)(Start.Y - node.Y);
                coeff2 = (double)(Start.X * node.Y - node.X * Start.Y) / (double)(Start.Y - node.Y);
                if (Start.Y > node.Y)
                {
                    if (End.X + coeff1 * End.Y + coeff2 <= 0)
                    {
                        return angle;
                    }
                    else
                    {
                        return (Math.PI * 2 - angle);
                    }
                }
                else if (Start.Y < node.Y)
                {
                    if (End.X + coeff1 * End.Y + coeff2 <= 0)
                    {
                        return (Math.PI * 2 - angle);
                    }
                    else
                    {
                        return angle;
                    }
                }
            }
            else if (Start.Y == node.Y)
            {
                if (node.X > Start.X)
                {
                    if (End.Y < Start.Y)
                    {
                        return angle;
                    }
                    else
                    {
                        return (Math.PI * 2 - angle);
                    }
                }
                else if (node.X < Start.X)
                {
                    if (End.Y < Start.Y)
                    {
                        return (Math.PI * 2 - angle);
                    }
                    else
                    {
                        return angle;
                    }
                }
            }
            return 10.0f;
        }

        #endregion


    }
}
